import random
import itertools
import operator as op
import copy

import libtcodpy as libtcod

import data
import ai

#
# CLASSES! #
#

class Rectangle(object):
    """
    a rectangular shape used for the bsp tree algorithm
    """
    def __init__(self, topleft, bottomright=None, size=None):
        """
        a data structure containing corners of a rectangle used for room generation. must provide either bottomright
            or size. if both are given, size is used and bottomright is overridden

        args:
            topleft: a coordinate (iterable or Location)

        kwargs:
            bottomright: a coordinate (iterable or Location), defaults to topleft + size
            size: a coordinate (iterable or Location), if not provided then defaults to bottomright - topleft
        """
        self.topleft = Location(topleft)
        if size:
            self.bottomright = topleft + size
            self.size = Location(size)
        else:
            self.bottomright = Location(bottomright)
            self.size = self.bottomright - self.topleft
        self.center = Location((self.topleft + self.bottomright))/(2,2)
        self.corners = [self.center, Location((self.bottomright[0],self.topleft[1])), self.bottomright, Location((self.topleft[0],self.bottomright[1])), self.topleft]
        self.brother = None
        self.father = None
        self.subrect = None
        x = random.randint(self.topleft[0]+1,self.bottomright[0]-1)
        y = random.randint(self.topleft[1]+1,self.bottomright[1]-1)
        self.stem = Location((x,y)) # a random point in the room to connect to via corridors

    def test(self, point):
        """
        check if point is inside this rectangle

        args:
            point: a Location

        returns:
            True if point is inside this rectangle, else False
        """
        return self.topleft[0] <= point[0] <= self.bottomright[0] and self.topleft[1] <= point[1] <= self.bottomright[1]

    def perimeter(self):
        """
        determine the perimeter of this rectangle

        returns:
            a set of Locations which represent the borders of this rectangle
        """
        walls = set()
        for x in range(self.topleft[0]-1,self.bottomright[0]+2):
            walls.add(Location((x,self.topleft[1]-1)))
            walls.add(Location((x,self.bottomright[1]+1)))
        for y in range(self.topleft[1],self.bottomright[1]+1):
            walls.add(Location((self.topleft[0]-1,y)))
            walls.add(Location((self.bottomright[0]+1,y)))
        return walls

    def split(self, place, vertical=True):
        """
        subdivide this rectangle into two smaller rectangles, making them children

        args:
            place: a coordinate (iterable or Location) indicating the spot to split into 2 sub rectangles

        kwargs:
            vertical: if True, split the rectangle vertically, else split horizontally, defaults to True

        returns:
            a list of the child rectangles
        """
        if vertical:
            child1 = Rectangle(topleft=self.topleft, size=(place, self.size[1]))
            child2 = Rectangle(topleft=self.topleft+(place, 0), bottomright=self.bottomright)
        else:
            child1 = Rectangle(topleft=self.topleft, size=(self.size[0], place))
            child2 = Rectangle(topleft=self.topleft+(0, place), bottomright=self.bottomright)
        child1.brother = child2
        child2.brother = child1
        child1.father = self
        child2.father = self
        return [child1, child2]

    def make_subrect(self, min_room_size=data.MIN_ROOM_SIZE, max_room_size=data.MAX_ROOM_SIZE):
        """
        make a smaller rectangle inside this one

        kwargs:
            min_room_size: an x, y pair indicating the smallest possible room, defaults to MIN_ROOM_SIZE in data.py
            max: an x, y pair indicating the largest possible room, defaults to MAX_ROOM_SIZE in data.py
        """
        width = random.randint(min_room_size[0], min(self.size[0]-2, max_room_size[0]))
        height = random.randint(min_room_size[1], min(self.size[1]-2, max_room_size[1]))
        left = random.randint(1, self.size[0]-width)
        top = random.randint(1, self.size[1]-height)
        self.subrect = Rectangle(self.topleft+(left,top), size=(width,height))

    def tree(self, min_leaf_size, min_room_size):
        """
        make a bsp tree, using this rectangle as the base node

        args:
            min_leaf_size: an x, y pair indicating the smallest possible rectangle to partition, BEFORE shrinking to a room
            min_room_size: an x, y pair indicating the smallest possible room

        returns:
         the final rooms, the orthogonal corridors connecting them
        """
        
        open_nodes = [self]
        leaves = []
        branches = []
        while open_nodes:
            node = open_nodes.pop()
            v = random.randint(0, 1)
            split = False
            i = 0
            while not split:
                if node.size[v] >= min_leaf_size[v]*2:            
                    place = random.randint(min_leaf_size[v], node.size[v]-min_leaf_size[v])
                    n1, n2 = node.split(place, not v)
                    open_nodes.append(n1)
                    open_nodes.append(n2)
                    branches.append(n1.center.o_path(n2.center))
                    split = True
                if i < 3:
                    v = int(not v)
                    i += 1
                else:
                    leaves.append(node)
                    node.make_subrect(min_room_size)
                    branches.append(node.subrect.center.o_path(node.center))
                    split = True
        return leaves, branches

    def __repr__(self):
        return 'Rectangle({}, {})'.format(self.topleft, self.bottomright)

    def __eq__(self, other):
        return self.topleft == other.topleft and self.size == other.size


class Infix(object):
    """
    a crappy class that lets you define infix functions and use them like: 3 |plus| 5
    """

    def __init__(self, function):
        self.function = function
    def __ror__(self, other):
        return Infix(lambda x, self=self, other=other: self.function(other, x))
    def __or__(self, other):
        return self.function(other)
    def __call__(self, value1, value2):
        return self.function(value1, value2)

class Location(tuple):
    """
    basically a tuple that supports addition and subtraction natively to make location calculations easier
    you need to use an iterable to construct it, not multiple values. ie, Location((0, 0)) NOT Location(0,0)
    """

    def _binaryop(self, other, op):
        """
        a method to perform an operation on this object and another object
        """
        return Location(op(a, b) for a, b in itertools.izip_longest(self, other, fillvalue=0))

    def _unaryop(self, op):
        """
        a method to perform an operation on this object
        """
        return Location(op(a) for a in self)

    def __add__(self, other):
        return self._binaryop(other, op.add)

    def __sub__(self, other):
        return self._binaryop(other, op.sub)

    def __div__(self, other):
        return self._binaryop(other, op.div)
        
    def __abs__(self):
        return Location(abs(v) for v in self)

    def __neg__(self):
        return self._unaryop(op.neg)

    def __rshift__(self, other):
        """
        lets you use the >> operator to return a path between this object and another location
        """
        return self.path(other)

    def __lshift__(self, other):
        """
        lets you use the << operator to return a path between another location and this object
        """
        return self.path(other)[-2::-1] + [self]

    def __gt__(self, other):
        """
        lets you use the > operator to return a path as a generator
        """
        return self.lazy_path(other)

    def distance(self, other):
        """
        return the distance between this location and another location

        args:
            other: another iterable, probably another Location object but it's not strictly required

        returns:
            a number representing the distance between the two locations
        """
        return max(abs(self - other))

    def neighborhood(self, d):
        """
        get the coordinates of all locations within d distance from this location

        args:
            d: a number representing the size of the neighborhood

        returns:
            a list of Location objects of the coordinates inside the neighborhood, including this location
        """
        offsets = xrange(-1*d, 1+d)
        x = [[v + i for i in offsets] for v in self]
        return [Location(v) for v in itertools.product(*x)]

    def path(self, other):
        """
        make a list of Location objects representing the direct path between 2 locations, including the other given point

        args:
            other: another iterable, probably another Location object but it's not strictly required

        returns:
            a list of Location objects, including 'other'
        """
        return list(self.lazy_path(other))

    def lazy_path(self, other):
        """
        make a generator of Location objects representing the direct path between 2 locations. same as path, but "lazy"

        args:
            other: another iterable, probably another Location object but it's not strictly required

        returns:
            a generator of Location objects, including 'other'
        """
        slope = other - self
        length = max(abs(slope))
        point = self
        for _ in range(length):
            point += Location([float(v)/length for v in slope])
            yield Location([int(round(v)) for v in point])

    def o_path(self, other, ordering=None):
        """
        make a list of Location objects representing a path between 2 locations, made up of orthogonal projections.

        args:
            other: another iterable, probably another Location object but it's not strictly required

        kwargs:
            ordering: a permutation of [0, 1, 2, ..., n] determining the order in which the n+1 axes are projected along.

        returns:
            a list of Locations, including 'other'
        """
        length = max(len(self),len(other))
        if not ordering:
            ordering = range(length)
        other = Location(other)
        point = self
        path = []
        for axis in ordering:
            if self[axis] < other[axis]:
                delta = 1
            else:
                delta = -1
            while point[axis] != other [axis]:
                point += (0,)*axis + (delta,) + (0,)*(length - axis - 1)
                path.append(point)
        return path

class Scene(object):
    """
    an area the player moves through
    """

    def __init__(self, width, height, floor_type, wall_type, danger_level=0, name='scene',
                 min_leaf_size=data.MIN_LEAF_SIZE, min_room_size=data.MIN_ROOM_SIZE, seed=None):
        """
        a data structure containing all the information about an area or game level

        args:
            width: an integer
            height: an integer
            floor_type: an integer corresponding to a terrain type
            wall_type: an integer corresponding to a terrain type

        kwargs:
            danger_level: an integer corresponding to a row in data.py's UNIT_TABLE and ITEM_TABLE, modeling how
                dangerous/rewarding the scene is by what is randomly spawned/forged there
            name: a string, defaults to 'scene'
            min_leaf_size: x, y pair setting the minimum partition in the tree before creating a room.
                defaults to MIN_LEAF_SIZE in data.py
            min_room_size: x, y pair setting the minimum size of a room. defaults to MIN_ROOM_SIZE in data.py
            seed: a random seed not actually used in map generation
        """
        self.width = width
        self.height = height
        self.floor_type = floor_type
        self.wall_type = wall_type
        self.danger_level = danger_level
        self.name = name
        self.seed = seed
        self.grid, self.rooms, self.doors = self.make_map()
        self.forget_map()
        self.dirty = set([])  # tiles to be updated
        self.units = set([])
        self.items = set([])
        self.traps = set([])
        self.stairs = set([])
        self.fov_map = libtcod.map_new(self.width, self.height)
        self.set_fov()

    def set_fov(self):
        """
        set walking and light-blocking properties of tiles
        """
        self.floors = {location for location in (Location((x, y)) for x in xrange(self.width) for y in xrange(self.height)) if self[location] == self.floor_type}
        self.floors = set()
        for y in range(self.height):
            for x in range(self.width):
                libtcod.map_set_properties(self.fov_map, x, y,
                                           not data.TERRAIN[self.grid[x][y]]['opaque'],
                                           not data.TERRAIN[self.grid[x][y]]['solid'])
                if not data.TERRAIN[self.grid[x][y]]['solid']:
                    self.floors.add(Location((x,y)))
        self.path = libtcod.path_new_using_map(self.fov_map)

    def kill(self, units):
        """
        remove the specified units from this scene

        args:
            units: a list of units to remove
        """
        for unit in units:
            unit.die()
        self.units = self.units.difference(units)

    def forget_map(self):
        """
        set each tile in the scene to unexplored, for initialization or forgetfulness
        """
        self.explored = [[0 for _ in range(self.height)]
                         for _ in range(self.width)]

    def make_map(self, min_leaf_size=data.MIN_LEAF_SIZE, min_room_size=data.MIN_ROOM_SIZE, max_room_size=data.MAX_ROOM_SIZE):
        """
        make a grid of integers corresponding to tile types, using a BSP tree algorithm. also 
            generates and stores useful information about the final rooms and doors.

        kwargs:
            min_leaf_size: x, y pair setting the minimum partition in the tree before creating a room.
                defaults to MIN_LEAF_SIZE in data.py
            min_room_size: x, y pair setting the minimum size of a room. defaults to MIN_ROOM_SIZE in data.py
            max_room_size: x, y pair setting the maximum size of a room. defaults to MAX_ROOM_SIZE in data.py

        returns:
            a grid of integers corresponding to tile types, a list of Rectangle objects corresponding to the rooms
                generated by the BSP tree algorithm, and a set of Locations corresponding to the doors generated.
            TODO: expand 'doors' to contain all spots that you should stop on during auto-travel: doorways, splittings, etc
        """
        floors = set()
        corridors = set()
        doors = set()
        orphaned_doors = set()
        rect = Rectangle((0,0), (data.MAP_WIDTH-2,data.MAP_HEIGHT-2))
        leaves, branches = rect.tree(min_leaf_size, min_room_size)
        for branch in branches:
            for tile in branch:
                corridors.add(tile)
        for leaf in leaves:
            floor = set()
            room = leaf.subrect
            for y in range(room.topleft[1],room.bottomright[1]+1):
                for x in range(room.topleft[0],room.bottomright[0]+1):
                    floors.add((x,y))
            door = room.perimeter().intersection(corridors)
            if door:
                for tile in door:
                    if len(set(tile.neighborhood(1)).intersection(door)) == 1:
                        doors.add(tile)
        for door in doors:
            if len(set(door.neighborhood(1)).intersection(floors)) > 6:
                orphaned_doors.add(door)
        doors.difference_update(orphaned_doors)
        grid = [[self.wall_type
                      for _ in range(self.height)] for _ in range(self.width)]
        for y in range(self.height):
            for x in range(self.width):
                if (x,y) in floors:
                    grid[x][y] = 0
                if (x,y) in corridors:
                    grid[x][y] = 0
                if (x,y) in doors:
                    grid[x][y] = 2
        return grid, [leaf.subrect for leaf in leaves], doors

    def random_floor_tile(self, room=None):
        """
        pick a random floor tile inside a random room in this scene.

        kwargs:
            room: a Rectangle full of possible Locations to be returned. defaults to a random room in this scene

        returns:
            a Location corresponding to randomly chosen tile
        """
        if not room:
            room = self.rooms[random.randint(0,len(self.rooms)-1)]
        return Location((random.randint(room.topleft[0],room.bottomright[0]),random.randint(room.topleft[1],room.bottomright[1])))
        
    def pathable_neighborhood(self, location, units_too=False, player_too=False):
        """
        make a set of Locations around the given location that are pathable

        args:
            location: a Location in this scene

        kwargs:
            units_too: a boolean flag for deciding if units are pathable, defaults to False

        returns:
            a set of Location objects
        """
        floors = self.floors.intersection(location.neighborhood(1))#{v for v in location.neighborhood(1) if v in self and self[v] == self.floor_type}
        if units_too:
            units = {unit.location for unit in self.units if not unit.is_player or unit.is_player is player_too}
            return floors.difference(units)
        else:
            return floors

    def spawn(self, unit=None, name=None, location=None, pushing=False):
        """
        place a unit into this scene. can specify a particular Unit instance to be placed, the name of a unit type 
            in UNIT_TABLE in data.py to be created, or leave unspecified to create and place a random unit based on 
            this scene's danger_level. can specify a location or use a random floor tile, and will place the unit on
            an adjacent tile if blocked, or push existing units aside.

        kwargs:
            unit: a Unit object to be placed in this scene. defaults to None
            name: a string determining the type of unit to be created, based on UNIT_TABLE in data.py
            location: the location in this scene to place the unit on (or near), defaults to None, then picks a random floor tile.
            pushing: whether or not to displace existing units (displaces this unit if False), defaults to False

        returns:
            fov_redraw: whether or not the fov needs to be redrawn
            output: data required for text output
        """
        fov_redraw = False
        if not unit:
            if not name:
                name = random.choice(data.UNIT_TABLE[random.randint(0, min(self.danger_level, len(data.UNIT_TABLE)-1))])
            unit = Unit(**data.UNITS[name])
        output = [('instant', 'A wild {} appeared.'.format(unit.name))]
        if location:
            unit.location = Location(location)
        if not location:
            unit.location = self.random_floor_tile()
        conflict = [v for v in self.units if v.location == unit.location]
        if conflict:
            adjacent = self.pathable_neighborhood(unit.location, True)
            if adjacent:
                if pushing:
                    conflict[0].location = adjacent.pop()
                    if conflict[0].is_player:
                        fov_redraw = True
                else:
                    unit.location = adjacent.pop()
            else:
                return fov_redraw, [('instant', 'no space at {} to spawn {}.'.format(unit.location, unit.name))]
        self.units.add(unit)
        unit.scene = self
        return fov_redraw, output

    def forge(self, item=None, name=None, location=None):
        """
        place an item into this scene. can specify a particular Item instance, a name in ITEM_TABLE in data.py to create
            and place, or leave unspecified to choose a random item based on this scene's danger_level. if a location is 
            not specified, chooses a random floor tile in this scene. checks for similar items in the chosen location and 
            increases quantities rather than adding more instances if applicable.

        kwargs:
            item: an Item to place. defaults to None, which chooses and creates a random item type in ITEM_TABLE in data.py
            name: the name of an item type to be forged from data.py's ITEM_TABLE
            location: the location the item is to appear.
        """
        if not item:
            if not name:
                name = random.choice(data.ITEM_TABLE[random.randint(0, min(self.danger_level, len(data.ITEM_TABLE)-1))])
            item = Item(**data.ITEMS[name])
        if location:
            item.location = location
        else:
            item.location = self.random_floor_tile()
        conflicts = {other for other in self.items if other.location == item.location and other.name == item.name}
        if conflicts:
            conflicts.pop().quantity += item.quantity
        else:
            self.items.add(item)

    def __contains__(self, item):
        """
        determine whether a location is within the scene boundaries or not. used like: >>> Location((4, 6)) in scene
                                                                                       True
        args:
            item: a location

        returns:
            True if the location is within the scene, otherwise False
        """
        return self.width > item[0] >= 0 and self.height > item[1] >= 0

    def __getitem__(self, item):
        """
        return the tile value of the given location, defaults to self.__missing__ if not within the scene boundaries

        args:
            item: a location

        returns:
            an int corresponding to the tile type (floor, wall, etc)
        """
        try:
            return self.grid[item[0]][item[1]]
        except IndexError:
            return self.__missing__()

    def __setitem__(self, key, value):
        """
        set the tile value of the given location

        args:
            key: the location to set
            value: an int value of the tile
        """
        self.grid[key[0]][key[1]] = value

    def __missing__(self):
        """
        return the basic wall

        returns:
            the int corresponding to the wall type of this scene
        """
        return self.wall_type




class Unit(object):
    """
    a man you make do stuff
    """

    def __init__(self, name='Unit', stats=None, skill_ranks=None, bonus_skills=None, location=Location((40, 25)), character='@',
                 equipment=None, inventory=None, abilities=set(), ai=ai.DefaultAI(), WAIT=None, scene=None, exp=0):
        """
        a monster or other thing that can perform actions

        kwargs:
            name: a string corresponding to the name of the unit, defaults to 'Unit'
            stats: a dictionary corresponding to the initial unit stats, defaults to {'strength': 1, 'stamina': 1, 'focus': 1}
            skill_ranks: a dictionary corresponding to the skill ranks the unit starts with, defaults to {}
            bonus_skills: a dictionary corresponding to the bonus skills the unit starts with, defaults to {}
            location: a Location object corresponding to the tile the unit spawns on, defaults to Location((40, 25))
            character: the display character representing this unit shown on the screen, defaults to '@'
            equipment: a dictionary corresponding to the starting equipment of this unit, defaults to {}
            abilities: a set of abilities this unit starts with, defaults to set()
            ai: the ai class used to decide which actions to take, defaults to ai.DefaultAI()
            WAIT: an integer representing how many frames this unit has to take before making an action, defaults to randint(1,10)
        """
        self.name = name
        self.scene = None
        self.alive = True
        if not bonus_skills: bonus_skills = dict.fromkeys(data.SKILL_LIST, 0)
        if not skill_ranks: skill_ranks = dict.fromkeys(data.SKILL_LIST, 0)
        if not equipment: equipment = {}
        if not inventory: inventory = []
        if not stats: stats = {'strength': 1, 'stamina': 1, 'focus': 1}
        self.base_stats = stats
        self.stats = {}
        for stat in self.base_stats:
            self.stats[stat] = self.base_stats[stat]

        # set skills and abilities, adding in any bonus_skills
        self.abilities = set([])
        for ability in abilities:
            self.gain_ability(ability)
        self.skills = {}
        self.skill_ranks = skill_ranks
        self.bonus_skills = bonus_skills

        # set misc. combat parameters
        self.move_stats = {}
        self.misc_stats = {}
        for stat in data.MISC_STATS:
            self.misc_stats[stat] = data.MISC_STATS[stat]

        # equip equipment and abilities
        self.equipment = dict.fromkeys(data.EQUIPMENT_SLOTS)
        for item in equipment:
            if self.scene:
                self.scene.forge(item=item)
            self.equip(item)

        # set basic parameters
        if not WAIT: WAIT = random.randint(1, 10)
        self.WAIT = WAIT
        self.character = character
        self.location = Location(location)
        self.scene = scene

        self.alter_stats()

        self.exp = exp
        self.ai = ai
        self.is_player = isinstance(self, Player)
        self.target = None
        self.destination = None
        self.path = None
        self.path_index = 0

        self.inventory = inventory
        self.burden = 0
        self.carrying_capacity = 100

    def alter_stats(self, stat_diffs={}, alter_base_stats=False):
        """
        change the stats of this Unit and update the skills based on the
            new stat values, then check for death

        args:
            stat_diffs: a dictionary of stat: integers which represents the amount
                to change each stat by. examples: {'strength': 2} or {'focus': -10, 'stamina': 1}

        kwargs:
            alter_base_stats: a Boolean determining whether the changes affect base_stats as well, default is False
        """

        for stat in stat_diffs:
            if alter_base_stats:
                self.base_stats[stat] += stat_diffs[stat]
            self.stats[stat] = min(self.stats[stat] + stat_diffs[stat], self.base_stats[stat])
            if self.stats[stat] < 0:
                self.stats[stat] = 0

        if 'strength' in stat_diffs and stat_diffs['strength'] < 0:
            if 'second wind' in self.abilities:
                self.alter_stats({'stamina':2})
        self.update_color()
        self.update_skills()
        if self.stats['strength'] <= 0:
            # TODO: Update all the code that touches this to look for the Unit.alive thing instead of the 'die' return
            self.alive = False
            return 'die'
        else:
            return None

    def update_skills(self):
        """
        update this Unit's skills taking stats and skill bonuses into account
        """
        # set skills based on CURRENT stats
        for stat in self.stats:
            for skill in data.SKILLS[stat]:
                self.skills[skill] = self.stats[stat]
        if 'fervor' in self.abilities:
            self.skills['force'] += (self.base_stats['strength'] - self.stats['strength'])
        if 'endurance' in self.abilities:
            self.skills['accuracy'] += (self.base_stats['stamina'] - self.stats['stamina'])
        # apply skill ranks earned, if any
        for skill in self.skill_ranks:
            self.skills[skill] += self.skill_ranks[skill]
        # apply bonuses due to equipment, etc, if any
        for skill in self.bonus_skills:
            self.skills[skill] += self.bonus_skills[skill]

    def update_bonus_skills(self, move_type='normal'):
        """ 
        set this Unit's bonus_skills based on previous actions

        kwargs:
            move_type: a string in data.BONUS_SKILLS
        """
        self.bonus_skills = data.BONUS_SKILLS[move_type]
        self.update_skills()

    def update_color(self):
        """
        set this Unit's display color based on current stats
        colors are in rgb format: strength is red, stamina is green, focus is blue
        """
        self.color = libtcod.Color(min(255, 0+40*self.stats['strength']),
                                   min(255, 0+40*self.stats['stamina']),
                                   min(255, 0+40*self.stats['focus']))

    def skill_up(self, skill, amount=1):
        """
        add skill levels to this Unit

        args:
            skill: a string corresponding to the skill to add to

        kwargs:
            amount: an integer amount to raise (or lower) the skill by, defaults to 1
        """
        if skill in self.skill_ranks:
            self.skill_ranks[skill] += amount
        else:
            self.skill_ranks[skill] = amount
        self.update_skills()

    def gain_ability(self, ability):
        """
        add an ability to this Unit

        args:
            ability: the ability to add
        """
        self.abilities.add(ability)

    def equip(self, item, slot=None, equip_all=False):
        """
        add an item to this Unit's equipment and apply bonuses from the item. unequips the old item, if applicable.
        Does nothing if slot is unspecified and item.slots[0]==None, i.e. the item doesn't equip.

        args:
            item: the item to equip

        kwargs:
            slot: where to equip the item, i.e. 'right hand'. 
            equip_all: Boolean indicating if we are to equip 1 or all of the item's quantity, all being the choice for ammo.
        """
        if not slot:
            slot = item.slots[0]
        if slot:
            old = self.equipment[slot]
            if old:
                self.unequip(old)
            if item.quantity > 1 and not equip_all:
                new = copy.copy(item)
                new.quantity = 1
                self.equipment[slot] = new
                item.quantity -= 1
            else:
                self.equipment[slot] = item
                if item in self.inventory:
                    self.inventory.remove(item)

            self.alter_stats(item.stats, alter_base_stats=True)
            for skill in item.skills:
                self.skills[skill] += item.skills[skill]
            for misc_stat in item.misc_stats:
                self.misc_stats[misc_stat] += item.misc_stats[misc_stat]
            for ability in item.abilities:
                self.abilities.add(ability)
        
    def unequip(self, item=None, slot=None):
        """
        remove an item from this Unit's equipment and remove the item bonuses. Can call by specifying either
            the item itself or the slot the item is equipped in.

        kwargs:
            item: the item to unequip, defaults to None.
            slot: slot to unequip. if specified, overrides 'item'
        """
        if slot:
            item = self.equipment[slot]
        else:
            slot = item.slots[0]
        if item and item in self.equipment.values():
            self.equipment[slot] = None
            pickup(self, item, weight=False)
            for stat in item.stats:
                self.base_stats[stat] -= item.stats[stat]
                self.stats[stat] -= item.stats[stat]
            for skill in item.skills:
                self.skills[skill] -= item.skills[skill]
            for misc_stat in item.misc_stats:
                self.misc_stats[misc_stat] -= item.misc_stats[misc_stat]
            self.update_skills()

    def take_turn(self, percepts):
        """
        decide which action to take using this Unit's AI functions

        args:
            percepts: a dictionary containing the 'senses' for the AI to use

        returns:
            a direction in which to move
            # TODO: work on the return values more, it should be able to handle
                more than just moving
        """
        self.update_bonus_skills() #reset bonuses
        if self.stats['stamina'] > 0:
            return self.ai.turn(percepts)
        else:
            self.WAIT += 10
            return 0, 0
    
    def regen(self):
        """
        decide whether or not to regenerate this Unit's stats, and do so if appropriate
        """
        for stat in self.stats:
            if self.stats[stat] < self.base_stats[stat]:
                self.misc_stats[stat + '_heal_count'] += 1
                if self.misc_stats[stat + '_heal_count'] >= self.misc_stats[stat + '_heal_time']:
                    self.alter_stats({stat:1})
                    self.misc_stats[stat + '_heal_count'] = 0

    def die(self):
        """
        kill this unit and drop a random loot
        """
        self.alive = False
        self.scene.forge(location=self.location)

class Player(Unit):
    """
    the player is probably a special enough case of unit to warrant an
        additional class
    """

    def __init__(self, name='You', stats=None, **kwargs):
        """
        a  special unit representing the player character

        kwargs:
            name: a string containing the player's name, defaults to 'You'
            stats: a dictionary of starting stats, defaults to None
            kwargs: the additional Unit class __init__ arguments
        """
        super(Player, self).__init__(name, stats, **kwargs)
        self.kill_dict = {}
        self.seen_dict = {}
        for level in data.UNIT_TABLE:
            for unit in level:
                self.kill_dict[unit] = 0
                self.seen_dict[unit] = 0
        self.exp = 0

    def take_turn(self):
        """
        take the player's turn
        TODO: put automated travel/search/whatever functions here, via ai.py?
        """
        pass

    def gain_exp(self, unit=None, killed=True, amount=0):
        """
        gain diminishing exp and increase appropriate counters for seeing/killing a unit, or just
            give a flat amount of exp.

        kwargs:
            unit: the unit that died. defaults to None
            killed: adds kill exp if True, seen exp if False. defaults to True
            amount: the amount of exp to add, if no unit is specified
        """
        if unit:
            if killed:
                self.exp += unit.exp/(self.kill_dict[unit.name] + 1)
                self.kill_dict[unit.name] += 1
            else:
                self.exp += unit.exp/(self.seen_dict[unit.name] + 1)
                self.seen_dict[unit.name] += 1
        else:
            self.exp += amount

class Item(object):
    """
    a thing that units can carry or equip
    """

    def __init__(self, name='Unidentified Item', character='|', color=None, 
                 stats=None, skills=None, misc_stats=None, abilities=None,
                 quantity=1, weight=1, slots=None, location=Location((0, 0))):
        """
        an object that a Unit can use

        kwargs:
            name: a string representing the item name, defaults to 'Unidentified Item'
            character: the display character representing this item shown on the screen, defaults to '@'
            color: a libtcod.Color object representing the display color of this item on screen
            stats: a dictionary representing item stats, defaults to {}
            skills: a dictionary of abilities granted by equipping this item, defaults to {}
            misc_stats: a dictionary representing the miscellaneous stats granted by this item, defaults to {}
            abilities: a set of abilities the item grants you when you equip it
            quantity: an integer quantity of this item
            weight: an integer weight of this item
            slots: a list of strings corresponding to the different slots the item can be equipped, defaults to [None]
            location: the location of this item, defaults to Location((0, 0))
        """
        if not slots: slots = [None]
        self.name = name
        self.character = character
        if not color: color = libtcod.Color(255, 255, 255)
        self.color = color
        if not stats: stats = {}
        self.stats = stats
        if not skills: skills = {}
        self.skills = skills
        if not misc_stats: misc_stats = {}
        self.misc_stats = misc_stats
        if not abilities: abilities = set()
        self.abilities = abilities
        self.quantity = quantity
        self.weight = weight
        self.location = location
        self.slots = slots

    def __repr__(self):
        return 'Item({})'.format(self.name)

    def __str__(self):
        return self.name

    def __eq__(self, other):
        return (isinstance(other, self.__class__) and
                self.__dict__ == other.__dict__)

    def __ne__(self, other):
        return not self.__eq__(other)


#
# FUNCTIONS! #
#

def move(unit, direction, move_type='normal'):
    """
    move a unit from 1 location in a scene to another, and adjust the unit's WAIT accordingly, attacks on collision

    args:
        unit: a Unit object that will be moved
        direction: a tuple containing the change in x and change in y, as in (dx, dy)

    kwargs:
        move_type: 'normal', 'sneak', or 'run', defaults to 'normal'

    returns:
        a string giving information on the result of the attempted move
    """
    tloc = unit.location + direction
    unit.update_bonus_skills(move_type)
    scene = unit.scene
    for target in scene.units:
        if target.location == tloc and target != unit:
            if not unit.is_player and not target.is_player:
                target.location = unit.location
                target.WAIT += target.misc_stats['move_time']+data.MOVE_STATS[move_type]['move_time']
                break
            result = attack(unit, target, move_type=move_type)
            if move_type == 'run':
                unit.alter_stats({'stamina': -1})
            if move_type == 'sneak':
                unit.alter_stats({'focus': -1*unit.stats['focus']})
            # update panel to display stats of unit just struck by player
            if unit.is_player and target.stats['strength'] > 0:
                unit.target = target
            unit.WAIT += unit.misc_stats['attack_time']+data.MOVE_STATS[move_type]['attack_time']
            return result
    # if no target was found, attempt to move to the target tile
    if not data.TERRAIN[scene.grid[tloc[0]][tloc[1]]]['solid']:
        scene.dirty.add(unit.location)
        unit.location = tloc
        unit.WAIT += unit.misc_stats['move_time']+data.MOVE_STATS[move_type]['move_time']
        if move_type == 'run' and direction != (0,0):
            unit.alter_stats({'stamina': -1})
        #if move_type == 'sneak' and direction != (0,0):
            #unit.alter_stats({'focus': -1})
        return 'moved'
    else:
        return 'cancelled'

def attack(attacker, target, genre='melee', move_type='normal', stealth=0, accuracy=0, force=0, lethality=0, daze=0, stun=0):
    """
    perform an attack against target. roll stealth vs detection to see if attack is guarded.
    if unguarded, deal lethality-resistance to strength and daze-clarity to focus.
    if guarded, roll accuracy vs evasion to see if attack is dodged
    if dodged, attack misses. otherwise, deal force-guard to stamina.
    currently, daze and lethality are not implemented elsewhere.

    args:
        attacker: the unit doing the attacking
        target: the unit being attacked

    kwargs:
        genre: the type of attack being performed, defaults to 'melee'
        move_type: 'normal', 'sneak' (stab), or 'run' (smash), defaults to 'normal'
        stealth: bonus stealth for the attack, defaults to 0
        accuracy: bonus accuracy for the attack, defaults to 0
        force: bonus force for the attack, defaults to 0
        lethality: bonus lethality for the attack, defaults to 1
        daze: bonus daze for the attack, defaults to 0
        stun: bonus stun for the attack, defaults to 0
        
    returns:
        a dictionary of attack results
    """
    hit = True
    piercing = roll(attacker.skills['stealth']+stealth, t=target.skills['detection'])
    pierced = piercing > data.PIERCING_REQ or target.stats['stamina'] <= 0
    dmg = roll(attacker.skills['force']+force, t=target.skills['guard'])
    hit = roll(attacker.skills['accuracy']+accuracy, t=target.skills['evasion'])
    if pierced:
        target.alter_stats({'strength': max(0, dmg)*-1})
    elif hit >= 0:
        if dmg > 0:
            target.alter_stats({'stamina': max(0, dmg)*-1})
            if 'stagger' in attacker.abilities:
                target.WAIT += dmg
                print 'stagger proc for {}'.format(dmg)
            if 'knockback' in attacker.abilities and dmg >= target.stats['strength'] and genre == 'melee':
                move(target, direction = target.location - attacker.location)
        else:
            if 'rebuke' in target.abilities:
                attacker.WAIT -= dmg
                print 'rebuke proc for {}'.format(dmg)
            if 'counter' in target.abilities and -1*dmg > attacker.stats['strength'] and genre == 'melee':
                print 'countered'
                return attack(target, attacker)
                    
    results = {'player': attacker.is_player,'attacker': attacker.name, 'target': target.name, 
               'move_type': move_type, 'pierced': pierced, 'hit': hit, 'amount': dmg
    }
    return results

def funeral(scene):
    """
    takes a scene, figures out which units should die, kills them, and returns the dead

    args:
        scene: the scene to be examined for dead units

    returns: the list of dead units if there are dead units, or False if there are not
    """
    the_dead = [unit for unit in scene.units if not unit.alive]
    if the_dead:
        #units = scene.units.difference(set(the_dead))
        scene.kill(set(the_dead))
        return the_dead
    return False

def update_game_state(scene, player):
    """
    update the state of the game

    args:
        scene: the current Scene the player is in
        player: the player unit object

    returns:
        fov_redraw: a boolean saying whether or not the fov needs to be redrawn
        output: the strings to be printed to the player
    """
    fov_redraw = False
    output = []
    for unit in scene.units:
        if unit.WAIT < 1:
            action = unit.take_turn({'player': player, 'self': unit, 'scene': scene})
            m = move(unit, action)
            if m == 'moved':
                pass
            elif m == 'cancelled':
                output.append('Can\'t move there')
            else:
                output.append(('attack', m))
        unit.regen()
        unit.WAIT -= 1
        the_dead = funeral(scene)
        if the_dead:
            for unit in the_dead:
                output.append('{} dies.'.format(unit.name))
                scene.dirty.add(unit.location)
                player.gain_exp(unit)
                if player.target == unit:
                    player.target = None

    return fov_redraw, output

def path(l1, l2):
    """
    takes 2 Locations and returns a list of Locations that are the optimal path from l1 to l2
    the returned list contains l2 as its last point

    args:
        l1: the starting Location
        l2: the ending Location

    returns:
        a list of Locations
    """
    slope = l2 - l1
    length = max(abs(slope))
    points = []
    point = l1
    for _ in range(length):
        point += Location([float(v) for v in slope]) / ([length]*max(len(l1), len(l2)))
        points.append(Location([int(round(v)) for v in point]))
    return points

@Infix
def dis(l1, l2):
    """
    return the distance between 2 Locations on a grid

    args:
        l1: the first Location
        l2: the second Location

    returns:
        the distance
    """
    return max(abs(l1 - l2))

def map_gen(name):
    """
    generate a scene

    args:
        name: a string representing the name of this game level

    returns:
        a Scene object
    """
    return Scene(data.MAP_WIDTH, data.MAP_HEIGHT, floor_type=0, wall_type=1,
                 name=name)

def roll(base, t=0, d=1, s=6, td=1, ts=6):
    """
    roll base + d s-sided dice vs t + td ts-sided dice

    args:
        base: an integer base score to add to the roll

    kwargs:
        t: the integer target base score to add to the roll to beat, defaults to 0
        d: the integer number of dice to roll, defaults to 1
        s: the integer number of sides on the rolled dice, defaults to 6
        td: the integer number of target dice to roll against, defaults to 1
        ts: the integer number of target dice sides, defaults to 6
    """
    roll = base
    if s:
        for i in range(d):
            roll += random.randint(1, s)
    goal = t
    if ts:
        for i in range(td):
            goal += random.randint(1, ts)
    return roll - goal

def pickup(unit, item, weight=True):
    """
    pickup an item. does not check for proximity

    args:
        unit: the unit trying to pick the item up
        item: the item to be picked up

    kwargs:
        weight: boolean determining if we adjust the unit's burden by the item's weight, defaults to True
            (we don't need to if we are moving items between inventory and equipment)
    """
    try:
        if item in unit.scene.items:
            unit.scene.items.remove(item)
    except AttributeError:
        pass
    if weight:
        unit.burden += item.weight*item.quantity
    conflicts = {v for v in unit.inventory if v.name == item.name}
    if conflicts:
        conflicts.pop().quantity += item.quantity
    else:
        unit.inventory.append(item)

def drop(unit, item, quantity=1, location=None):
    """
    drop an item, adjusting burden

    args:
        unit: the unit dropping the item
        item: the item to be dropped

    kwargs:
        quantity: the amount of item to be dropped, defaults to 1
        location: where the item will appear, defaults to the unit's location
    """
    if not location:
        location = unit.location
    if quantity >= item.quantity:
        quantity = item.quantity
        unit.inventory.remove(item)
    else:
        item.quantity -= quantity
        new_item = copy.copy(item)
        new_item.quantity = quantity
        item=new_item
    unit.burden -= item.weight*quantity
    unit.scene.forge(item=item, location=location)

def a_star(start, goal, graph, unit_check=True):
    """
    make a path from the start to the goal

    args:
        start: the starting Location
        goal: the Location to path to
        graph: a scene to navigate through

    kwargs:
        unit_check: a boolean determining whether units block paths or not, defaults to True

    returns:
        a list of Locations representing the found path, or the starting location wrapped in a list if no path is
            found
    """
    open_set = {start}
    closed_set = set()
    came_from = {}

    g_score = {start: 0}
    f_score = {start: start.distance(goal)}

    i = 0

    def retrace_path(c):
        def parent_gen(c):
            while c:
                yield c
                if came_from[c] != start:
                    c = came_from[c]
                else:
                    break
        result = [element for element in parent_gen(c)]
        result.reverse()
        return result

    while open_set:
        i += 1
        current = min(open_set, key=f_score.get)
        if current == goal:
            if i > 1:
                return retrace_path(current)
        open_set.remove(current)
        closed_set.add(current)
        for neighbor in graph.pathable_neighborhood(current, unit_check):
            tentative_g_score = g_score[current] + 1
            if neighbor in closed_set:
                if tentative_g_score >= g_score[neighbor]:
                    continue
            if neighbor not in open_set or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + neighbor.distance(goal)
                if neighbor not in open_set:
                    open_set.add(neighbor)
    return [start]
if __name__ == '__main__':
    x = Location((0, 0))
    print (x > Location((4, 8))).next()
    import timeit
    number = 1
    t = timeit.repeat('Location((0, 0)).path(Location((45,67)))', 'from __main__ import Location', number=number, repeat=1000)
    print sum(t)
    t2 = timeit.repeat('list(Location((0, 0)).lazy_path(Location((45,67))))', 'from __main__ import Location', number=number, repeat=1000)
    print sum(t2)
    print (sum(t) - sum(t2)) / sum(t) * 100
